home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 5 / SOUND_KI / HUFFMAN.C < prev    next >
Text File  |  1991-10-04  |  12KB  |  545 lines
  1. /*
  2. >>    Huffman.c            Project STORM
  3. >>
  4. >>    Copyright ⌐1990, Juri Munkki
  5. >>
  6. >>    This file contains compression routines for the sound
  7. >>    data of Project STORM. It uses the Huffman algorithm.
  8. */
  9.  
  10. #include "Huffman.h"
  11. #include "Shuddup.h"
  12. #include "asm.h"
  13.  
  14. Handle    PlainHand;        /*    Handle to contain uncompressed sounds.    */
  15. long    PlainSize;        /*    Size when uncompressed.                    */
  16.  
  17. int            MaxCodeLen;    /*    Longest binary coding used.                */
  18. long        MsgBitSize;    /*    Number of bits in the compressed data.    */
  19. Handle        MsgHand;    /*    Compressed data.                        */
  20. treenode    **QuickTable;    /*    Quick lookup table for uncompress.    */
  21.  
  22. treenode    Nodes[VALUES*2];    /*    Huffman encoding tree.            */
  23. treenode    *Sorted[VALUES];    /*    Table of remaining subtrees.    */
  24. int            UsedNodes;            /*    Number of nodes used.            */
  25. int            numsorted;            /*    Number of remaining subtrees.    */
  26.  
  27. /*    Prototypes:
  28. */
  29. treenode *GetSmallest(void);
  30. void CombineNode(treenode *node0, treenode *node1);
  31. void AssignCode(treenode *node, int len, long code);
  32. void DeriveSound(void);
  33. Handle    ReadDataFiles(long ftype);
  34.  
  35. /*
  36. >>    This routine writes the bit patterns in the compressed
  37. >>    form. It's fairly slow on 68000 and 68010 machines, but
  38. >>    works quickly on others.
  39. */
  40. void    OutputPhase()
  41. {
  42.     register    Handle    Outdata;
  43.     register    long    *OutP;
  44.     register    char    *SrcP;
  45.     register    long    bitpos,data;
  46.     register    long    bitwidth;
  47.     register    int        i;
  48.                 long    codes[VALUES];
  49.                 int        lens[VALUES];
  50.     
  51.     Outdata=GetResource(SKRESTYPE,SKHUFFMANN);
  52.  
  53.     SetHandleSize(Outdata,sizeof(long)*VALUES+(MsgBitSize+7)/8);    
  54.     if(!MemErr)
  55.     {    OutP=(long *)*Outdata;
  56.         SrcP=*PlainHand;
  57.         for(i=0;i<VALUES;i++)
  58.         {    *OutP++=Nodes[i].freq;
  59.             codes[i]=Nodes[i].code;
  60.             lens[i]=Nodes[i].codelen;
  61.         }
  62.         bitpos=0;
  63.         
  64.         if(CPUFlag<2)    /*    Incredibly slow version for 68000 & 68010 processors.    */
  65.         {    while(bitpos<MsgBitSize)
  66.             {    data=codes[*SrcP];
  67.                 i=lens[*SrcP++];
  68.                 bitwidth = 1L <<(i-1);
  69.                 
  70.                 while(i--)
  71.                 {    if(data & bitwidth)    BitSet(OutP,bitpos++);
  72.                     else                BitClr(OutP,bitpos++);
  73.                     data <<= 1;
  74.                 }
  75.             }
  76.         }
  77.         else            /*    Much faster version for real processors...            ;-)    */
  78.         {    while(bitpos<MsgBitSize)
  79.             {    data=codes[*SrcP];
  80.                 bitwidth=lens[*SrcP++];
  81.                 asm    68020
  82.                     {    BFINS    data,(OutP){bitpos:bitwidth}
  83.                         add.l    bitwidth,bitpos
  84.                     }
  85.             }
  86.         }
  87.     }
  88.     else
  89.         DebugStr("\PHuffmann failed");
  90.     ChangedResource(Outdata);
  91.     WriteResource(Outdata);
  92. }
  93.  
  94. /*
  95. >>    GetSmallest returns the subtree with the
  96. >>    lowest frequency count. It is used to find
  97. >>    the two lowest counts that are to be combined
  98. >>    into a new subtree.
  99. */
  100. treenode    *GetSmallest()
  101. {
  102.     register    int            i;
  103.     register    int            small;
  104.     register    long        freq;
  105.     register    treenode    *found;
  106.     
  107.     i=small=numsorted-1;
  108.     freq=Sorted[numsorted-1]->freq;
  109.  
  110.     while(i--)
  111.     {    if(Sorted[i]->freq<freq)
  112.         {    small=i;
  113.             freq=Sorted[i]->freq;
  114.         }
  115.     }
  116.     found=Sorted[small];
  117.     Sorted[small]=Sorted[--numsorted];
  118.     return    found;
  119. }
  120. /*
  121. >>    Create a new node out of the two nodes (subtrees)
  122. >>    that are given as parameters.
  123. */
  124. void    CombineNode(node0,node1)
  125. treenode    *node0,*node1;
  126. {
  127.     register    treenode    *newnode;
  128.     
  129.     newnode=&Nodes[UsedNodes++];
  130.     newnode->value=0xFF;
  131.     newnode->codelen=0;
  132.     newnode->code=0;
  133.     newnode->freq=node0->freq+node1->freq;
  134.     newnode->zeroptr=node0;
  135.     newnode->oneptr=node1;
  136.     newnode->typeflag=-1;
  137.     
  138.     Sorted[numsorted++]=newnode;
  139. }
  140. /*
  141. >>    Recursively assigned a binary code
  142. >>    pattern to all nodes. (This is the
  143. >>    final step of the stage that determines
  144. >>    the encoding.)
  145. */
  146. void    AssignCode(node,len,code)
  147. treenode    *node;
  148. int            len;
  149. long        code;
  150. {
  151.     node->code=code;
  152.     node->codelen=len;
  153.     
  154.     if(node->typeflag)
  155.     {    AssignCode(node->zeroptr,len+1,code*2);
  156.         AssignCode(node->oneptr,len+1,code*2+1);
  157.     }
  158.     if(len>MaxCodeLen)
  159.         MaxCodeLen=len;
  160. }
  161. /*
  162. >>    The sound samples are run through this
  163. >>    filter before they are packed. Packing
  164. >>    the differences makes Huffman encoding
  165. >>    much more efficient.
  166. */
  167. void    DeriveSound()
  168. {
  169.     register    long    i;
  170.     register    char    *p;
  171.     register    char    delta,val;
  172.  
  173.     p=*PlainHand;
  174.     for(i=PlainSize;i;i--)
  175.     {    *p= (*p >> DROPBITS) & ANDMASK;
  176.         p++;
  177.     }
  178.  
  179.     p=*PlainHand;
  180.     delta=128>>DROPBITS;
  181.     for(i=PlainSize;i;i--)
  182.     {    val=*p;
  183.         *p++=(val-delta) & ANDMASK;
  184.         delta=val;
  185.     }
  186.     
  187. }
  188. /*
  189. >>    Build a tree out of the frequency
  190. >>    counts. This routine is used for
  191. >>    packing and unpacking of data.
  192. */
  193. void    HuffmannTree()
  194. {
  195.     register    long        i;
  196.     register    treenode    *small1,*small2;
  197.  
  198.     /*    Create pointers for used nodes.
  199.     */
  200.     numsorted=0;
  201.     for(i=0;i<VALUES;i++)
  202.     {    if(Nodes[i].freq)
  203.         {    Sorted[numsorted++]=&Nodes[i];
  204.         }
  205.     }
  206.     
  207.     /*    Huffmann tree generation.
  208.     */
  209.     while(numsorted>1)
  210.     {    small1=GetSmallest();
  211.         small2=GetSmallest();
  212.         CombineNode(small1,small2);
  213.     }
  214.  
  215.     /*    Assign bit strings to tree nodes.
  216.     */
  217.     MaxCodeLen=0;    
  218.     AssignCode(Sorted[0],0,0);
  219.     
  220.     /*    Calculate useful statistics.
  221.     */
  222.     MsgBitSize=0;    /*    Size of output in bits.                    */
  223.     for(i=0;i<VALUES;i++)
  224.     {    MsgBitSize+=Nodes[i].freq*Nodes[i].codelen;
  225.     }
  226. }
  227. /*
  228. >>    Compress the sound files in the current
  229. >>    directory and store the compressed data
  230. >>    in a pair of resources.
  231. */
  232. void    DoCompress()
  233. {
  234.     register    long        i,j;
  235.     register    char        *p;
  236.     
  237.     /*    First, read the data from disk:
  238.     */
  239.     PlainHand=ReadDataFiles(SOUNDFILE);
  240.     PlainSize=GetHandleSize(PlainHand);
  241.     HLock(PlainHand);
  242.  
  243.     /*    Do a delta operation on the sound and divide by 2.
  244.     */
  245.     DeriveSound();
  246.  
  247.     /*    Initialize node values.
  248.     */
  249.     for(i=0;i<VALUES;i++)
  250.     {    Nodes[i].value=i;
  251.         Nodes[i].codelen=0;
  252.         Nodes[i].code=0;
  253.         Nodes[i].freq=0;
  254.         Nodes[i].zeroptr=0;
  255.         Nodes[i].oneptr=0;
  256.         Nodes[i].typeflag=0;
  257.     }
  258.  
  259.     /*    Make a frequency count.
  260.     */
  261.     p=*PlainHand;
  262.     for(i=PlainSize;i;i--)
  263.     {    Nodes[*p++].freq++;
  264.     }
  265.     UsedNodes=VALUES;
  266.  
  267.     /*    Frequency plot in window.
  268.     */    
  269.     for(i=0;i<VALUES;i++)
  270.     {    j=200-(Nodes[i].freq*1000)/PlainSize;
  271.         MoveTo(i,j);
  272.         LineTo(i,j);
  273.     }
  274.  
  275.     /*    Generate the tree and bit strings.
  276.     */
  277.     HuffmannTree();
  278.  
  279.     if(MaxCodeLen<=32)
  280.     {    OutputPhase();
  281.     }
  282.     else
  283.     {    SysBeep(10);    /*    This should never happen.    */
  284.         DebugStr("\PHuffmann failed.");
  285.     }
  286.     HUnlock(PlainHand);
  287.     DisposHandle(PlainHand);
  288. }
  289. /*
  290. >>    DeCompress only handles the more generic part
  291. >>    of the sound decompression. It reads the packed
  292. >>    data and frequency counts. The frequency counts
  293. >>    are used to rebuild the same tree that was used
  294. >>    for compression. A fast lookup table is then
  295. >>    built so that multiple bits can be decoded at
  296. >>    once.
  297. */
  298. void    DeCompress()
  299. {    
  300.     register    long    *MsgPtr;
  301.     register    long    i,j;
  302.             treenode    *TheNode;
  303.  
  304.     QuickTable=(treenode **)NewPtr(sizeof(treenode)*(1<<QTBITS));
  305.     MsgHand=GetResource(SKRESTYPE,SKHUFFMANN);
  306.     HLock(MsgHand);
  307.     MsgPtr=(long *)*MsgHand;
  308.     
  309.     PlainSize=0;
  310.     /*    Initialize node values.
  311.     */
  312.     for(i=0;i<VALUES;i++)
  313.     {    Nodes[i].value=i;
  314.         Nodes[i].codelen=0;
  315.         Nodes[i].code=0;
  316.         Nodes[i].freq=*MsgPtr++;
  317.         Nodes[i].zeroptr=0;
  318.         Nodes[i].oneptr=0;
  319.         Nodes[i].typeflag=0;
  320.         
  321.         PlainSize+=Nodes[i].freq;
  322.     }
  323.     UsedNodes=VALUES;
  324.  
  325.     /*    Generate the tree and bit strings.
  326.     */
  327.     HuffmannTree();
  328.  
  329.     /*    Set up a table for quick access for the QTBITS first levels
  330.     **    of the tree.
  331.     */
  332.     for(i=0;i<(1<<QTBITS);i++)
  333.     {    QuickTable[i]=0;
  334.     }
  335.     for(i=UsedNodes;i>=0;i--)
  336.     {    if(Nodes[i].freq && Nodes[i].codelen<=QTBITS)
  337.         {    QuickTable[Nodes[i].code<<(QTBITS-Nodes[i].codelen)]=&Nodes[i];
  338.         }
  339.     }
  340.  
  341.     for(i=0;i<(1<<QTBITS);i++)
  342.     {    if(QuickTable[i])        TheNode=QuickTable[i];
  343.         else                    QuickTable[i]=TheNode;
  344.     }
  345.     
  346. }
  347. /*
  348. >>    This routine first runs the previous one
  349. >>    and then uses the tree and the lookup table
  350. >>    to decode the data. Every sound is also
  351. >>    processed so that it can be efficiently
  352. >>    played with the sound kit.
  353. */
  354. void    DecodeSounds()
  355. {
  356.                 Handle        sinfo;
  357.                 Ptr            sdatap;
  358.                 long        *infop;
  359.                 int            i;
  360.  
  361.                 treenode    **QTable;
  362.     register    treenode    *TheNode;
  363.     register    Ptr            MsgData;
  364.  
  365.     register    long        bitpos,data;
  366.     register    long        count;
  367.     register    char        delta;
  368.     register    long        len;
  369.  
  370.                 int            sampleframes;
  371.                 int            samplepad;
  372.  
  373.     
  374.     if(OldSound)            /*    The sounds are padded so that they in samplepad-sized packets.    */
  375.     {    sampleframes=185;    /*    Each packet contains samplesframes bytes of data.                */
  376.         samplepad=188;
  377.     }
  378.     else
  379.     {    sampleframes=512;    /*    If the sound manager is used, no padding is necessary, but the    */
  380.         samplepad=512;        /*    sound length has to be a multiple of 512.                        */
  381.     }
  382.  
  383.     QTable=QuickTable;
  384.  
  385.     sinfo=GetResource(SKRESTYPE,SKSTABLE);
  386.     NumSounds=GetHandleSize(sinfo)/sizeof(long);
  387.     HLock(sinfo);
  388.     infop=(long *)*sinfo;
  389.  
  390.     len=0;
  391.     for(i=0;i<NumSounds;i++)
  392.     {    len+=((infop[i]+(sampleframes-1))/sampleframes)*samplepad;
  393.     }
  394.     
  395.     HUnlock(MsgHand);
  396.  
  397.     SKPtr=NewPtr(len+sizeof(SoundStuff)*(long)NumSounds);
  398.     if(MemErr)
  399.     {    NumSounds=0;
  400.         return;
  401.     }
  402.  
  403.     HLock(MsgHand);
  404.     MsgData=(sizeof(long)*VALUES)+*MsgHand;
  405.  
  406.     Sounds=(void *)SKPtr;
  407.     sdatap=SKPtr+sizeof(SoundStuff)*(long)NumSounds;
  408.     
  409.     for(i=0;i<NumSounds;i++)
  410.     {    len=((infop[i]+(sampleframes-1))/sampleframes)*samplepad;
  411.         Sounds[i].Poin=sdatap;
  412.         Sounds[i].Len=len;
  413.         Sounds[i].Count=len/samplepad;
  414.         sdatap+=len;
  415.     }
  416.  
  417.     delta=128>>DROPBITS;
  418.     bitpos=0;
  419.  
  420.     for(i=0;i<NumSounds;i++)
  421.     {    sdatap=Sounds[i].Poin;
  422.         len=infop[i];
  423.         count=sampleframes;
  424.  
  425.         if(CPUFlag<2)        /*    Check for processor type.                */
  426.         {    while(len--)    /*    Version for 68000 and 68010 processors.    */
  427.             {
  428.                 asm
  429.                     {    cmp.b    #16,bitpos
  430.                         blt.s    @nobitshift
  431.                         sub.b    #16,bitpos
  432.                         lea        2(MsgData),MsgData
  433.                     @nobitshift
  434.                         move.l    (MsgData),data
  435.                         move.l    bitpos,D0
  436.                         add.b    #QTBITS,D0
  437.                         rol.l    D0,data
  438.                         and.l    #((1<<QTBITS)-1),data
  439.                     }
  440.                     TheNode=QTable[data];
  441.     
  442.                 if(TheNode->typeflag)
  443.                 {    bitpos+=QTBITS;
  444.                     asm    {
  445.                     @begin0        cmp.b    #16,bitpos
  446.                                 blt.s    @nobitshifteither
  447.                                 sub.b    #16,bitpos
  448.                                 lea        2(MsgData),MsgData
  449.                     @nobitshifteither
  450.                                 move.l    (MsgData),data
  451.                                 addq.l    #1,bitpos
  452.                                 rol.l    bitpos,data
  453.                                 bcc.s    @zeropoint0
  454.                             
  455.                                 move.l    OFFSET(treenode,oneptr)(TheNode),TheNode
  456.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  457.                                 bne.s    @begin0
  458.                                 bra.s    @loopdone0
  459.                     @zeropoint0    move.l    OFFSET(treenode,zeroptr)(TheNode),TheNode
  460.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  461.                                 bne.s    @begin0
  462.                     @loopdone0        
  463.                     }
  464.                 }
  465.                 else
  466.                 {    bitpos+=TheNode->codelen;
  467.                 }
  468.                 delta+=TheNode->value;
  469.                 delta&=ANDMASK;
  470.                 *sdatap++=delta;
  471.                 if(!--count)
  472.                 {    count=samplepad-sampleframes;
  473.                     while(count--)
  474.                         *sdatap++=delta;
  475.     
  476.                     count=sampleframes;
  477.                 }
  478.             }
  479.             
  480.             if(count!=sampleframes)
  481.             {    count=(count+samplepad-sampleframes) % samplepad;
  482.                 while(count--)
  483.                 {    *sdatap++=delta;
  484.                 }
  485.             }
  486.         }
  487.         else    /*    Version for 68020, 68030, 68040 processors    */
  488.         {    while(len--)
  489.             {
  490.                 asm    68020
  491.                     {
  492.                     bfextu    (MsgData){bitpos:QTBITS},data
  493.                     }
  494.                     TheNode=QTable[data];
  495.     
  496.                 if(TheNode->typeflag)
  497.                 {    bitpos+=QTBITS;
  498.                     asm    68020
  499.                     {
  500.                     @begin
  501.                                 bfextu    (MsgData){bitpos:1},data
  502.                                 beq.s    @zeropoint
  503.                                 move.l    OFFSET(treenode,oneptr)(TheNode),TheNode
  504.                                 addq.l    #1,bitpos
  505.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  506.                                 bne.s    @begin
  507.                                 bra.s    @loopdone
  508.                     @zeropoint    move.l    OFFSET(treenode,zeroptr)(TheNode),TheNode
  509.                                 addq.l    #1,bitpos
  510.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  511.                                 bne.s    @begin
  512.                     @loopdone        
  513.                     }
  514.                 }
  515.                 else
  516.                 {    bitpos+=TheNode->codelen;
  517.                 }
  518.                 delta+=TheNode->value;
  519.                 delta&=ANDMASK;
  520.                 *sdatap++=delta;
  521.                 if(!--count)
  522.                 {    count=samplepad-sampleframes;
  523.                     while(count--)
  524.                         *sdatap++=delta;
  525.     
  526.                     count=sampleframes;
  527.                 }
  528.             }
  529.             
  530.             if(count!=sampleframes)
  531.             {    count=(count+samplepad-sampleframes) % samplepad;
  532.                 while(count--)
  533.                 {    *sdatap++=delta;
  534.                 }
  535.             }
  536.         }
  537.     }
  538.     
  539.     HUnlock(sinfo);
  540.     ReleaseResource(sinfo);
  541.     HUnlock(MsgHand);
  542.     ReleaseResource(MsgHand);
  543.     DisposPtr(QuickTable);    
  544. }
  545.